/*
[编程题]2-4 再战0-1背包问题
time:20210320 23:13 PM
key:1.列要从0-m+1，因为和实际体积有联系。
行从0开始是可以的，但是要对第一行做特殊处理，因为递归中是要从上一行拿东西。
user：ldc
*/

#include <iostream>
#include<iomanip>  
#include <iterator>
#include<stack>
#include<algorithm>
#include<queue>
#include<vector>
#include<math.h>
using namespace std;
int Max(int a, int b)
{
	if (a > b)
	{
		return a;
	}
	else
	{
		return b;
	}
}
int F(int** M, vector<int>&space, vector<int>&value, int i, int j)
{
	//行是考虑编号i及以前，下面的递归都涉及上一行，因此第一行要特殊求出。
	if (i==0)
	{
		if (space[i] > j)
		{//那就是相同体积下不考虑最新i物品的价值了
			return 0;
		}
		else
		{
			return value[i];
		}
	}
	//这第i个物品的体积暂时较大，装不下的情况
	if (space[i] > j)
	{//那就是相同体积下不考虑最新i物品的价值了
		return M[i - 1][j];
	}
	else
	{//不装第i个物品和装了第i个哪个更大。第二个换成M[i]就变成继续考虑当前行的i，就是同个i加多次，当然i==0时也要改。
		return Max(M[i - 1][j],M[i-1][j-space[i]]+value[i]);
	}
}
int main()
{

	//健身房
	vector<int>space;
	//公司
	vector<int>value;
	int i, n, m, x, j;
	cin >> n >> m;

	for (i = 0; i < n; i++)
	{
		cin >> x;
		space.push_back(x);
	}
	for (i = 0; i < n; i++)
	{
		cin >> x;
		value.push_back(x);
	}

	//做一个二维矩阵,注意是n(因为是编号，所以不需要n+1)和m+1(由于体积是要与输入的体积做比较，所以要+1);
	m++;
	int** M = new int* [n];
	for (i = 0; i < n; i++)
	{
		M[i] = new int[m];
		for (j = 0; j < m; j++)
		{
			M[i][j] = 0;
		}
	}
	//逐行放入(随着背包空间扩大，考虑放入前i个物品)
	for (i = 0; i < n; i++)
	{
	
		for (j = 0; j < m; j++)
		{
			M[i][j]=F(M,space,value,i,j);
			cout << M[i][j]<<"\t";
		}
		cout << endl;
	}
}

